package pers.qianyu.month_202012.date_20201214;

import org.junit.*;

import java.util.*;

/**
 * 279. 完全平方数
 * https://leetcode-cn.com/problems/perfect-squares/
 *
 * @author mizzle rain
 * @date 2020-12-14 21:34
 */
public class NumSquares {
    // 变种凑零钱问题
    public int numSquares(int n) {
        ArrayList<Integer> nums = new ArrayList<>();
        int a = 1;
        while (a * a <= n) {
            nums.add(a * a);
            a++;
        }
        int[] dp = new int[n + 1];
        for (int j = 0; j < dp.length; j++) {
            dp[j] = j;
        }
        for (int k = 1; k < dp.length; k++) {
            for (int num : nums) {
                if (k - num >= 0) {
                    dp[k] = Math.min(dp[k], dp[k - num] + 1);
                }
            }
        }
        return dp[dp.length - 1];
    }

    @Test
    public void test1() {
        int result = new NumSquares().numSquares(12);
        System.out.println("result = " + result);
    }
}
